package LC;

/**
 * https://leetcode.com/problems/linked-list-cycle-ii/description/
 * Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
 * Note: Do not modify the linked list.
 * Follow up:
 * Can you solve it without using extra space?
 */
public class LC_142_LinkedListCycleII_LinkedList {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = head.next;
        ListNode h1 = Solution.detectCycle(head);
        System.out.println(h1.val);
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    static class Solution {
        static ListNode detectCycle(ListNode head) {
            if (head == null || head.next == null) return null;
            // 快指针fp和慢指针sp，
            ListNode fp = head, sp = head;
            while (fp != null && fp.next != null) {
                sp = sp.next;
                fp = fp.next.next;
                //此处应该用fp == sp ，而不能用fp.equals(sp) 因为链表为1 2 的时候容易
                //抛出异常
                if (fp == sp) {  //说明有环
                    break;
                }
            }
            //System.out.println( fp.val + "   "+ sp.val );
            if (fp == null || fp.next == null) {
                return null;
            }
            //说明有环，求环的起始节点
            sp = head;
            while (fp != sp) {
                sp = sp.next;
                fp = fp.next;
            }
            return sp;
        }
    }
}